#!/usr/bin/env python

class Stack:
    def __init__(self):
        self._stack = []

    def __len__(self):
        return len(self._stack)

    def push(self, val):
        self._stack.append(val)

    def pop(self):
        return self._stack.pop() if len(self._stack) > 0 else None

    def peek(self):
        return self._stack[-1] if len(self._stack) > 0 else None

    def is_empty(self):
        return len(self._stack) == 0

def parentheses_matching(symbols):
    def matcher(ch1, ch2):
        return "{[(".index(ch1) == "}])".index(ch2)

    stack = Stack()

    for ch in symbols:
        if ch in "{[(":
            stack.push(ch)
        elif ch in "}])":
            if len(stack) > 0 and matcher(stack.peek(), ch):
                stack.pop()
            else:
                return False
    
    return len(stack) == 0

def base_transform(num, base = 2):
    digits = '0123456789ABCDEF'

    stack = Stack()
    while num >= base:
        num, rem = divmod(num, base)
        stack.push(rem)
    stack.push(num)

    ans = ""
    while len(stack) > 0:
        ans += digits[stack.pop()]
    
    return ans

def statement_transform(expr):
    priority  = {"*" : 3, "/" : 3, "+" : 2, "-" : 2, "(" : 1}
    op_stack = Stack()
    postfix_list = []

    for ch in expr:
        if ch in '01234567':
            postfix_list.append(ch)
        elif ch == "(":
            op_stack.push(ch)
        elif ch == ")":
            token = op_stack.pop()
            while token != "(":
                postfix_list.append(token)
                token = op_stack.pop()
        else:
            while not op_stack.is_empty() and priority[op_stack.peek()] >= priority[ch]:
                postfix_list.append(op_stack.pop())
            op_stack.push(ch)
    
    while not op_stack.is_empty():
        postfix_list.append(op_stack.pop())

    return "".join(postfix_list)


import operator

def expression_evaluate(expr):
    operation = {'+' : operator.add,
                 '-' : operator.sub,
                 '*' : operator.mul,
                 '/' : operator.truediv}
    opran_stack = Stack()

    for ch in expr:
        if ch in "+-*/":
            oprand1 = opran_stack.pop()
            oprand2 = opran_stack.pop()
            oprand_stack.push(operation[ch](oprand1, oprand2))
        else:
            opran_stack.push(int(ch))

    return opran_stack[0]


if __name__ == "__main__":
    s = Stack()
    s.push(5)
    s.push(4)
    print(s.pop())
    print(s.pop())
    s.push(3)
    print(len(s))
    print(s.peek())
    print(len(s))
    print(parentheses_matching("{[()()][()]}"))
    print(parentheses_matching("{[()()[()]}"))
    print(base_transform(20))
    print(base_transform(27, 16))
    print()